Файл: GraphSearch.txt
Дата: 10.04.2014
1:
2:
3:
4:
5:
6: присвоить ШИРИНА_МАКС 8 ВЫСОТА_МАКС 8
7: присвоить ШАГ_РЕШЕТКИ 60
8: присвоить ЦВЕТ_ВЕРШИНЫ 14 РАДИУС_ВЕРШИНЫ 20
9: присвоить ЦВЕТ_РЕБРА 4 ЦВЕТ_ВЕРШИНЫ_ВЫД 10
10:
11: Сгенерить_граф
12: Найти_путь
13: Показать_граф
14:
15:
16:
17: функция Сгенерить_граф
18: память локальный ширина список_высота список_высота_выбраны выбран \
19: предыдущая_вершина список_высота_выбраны_пред ширина_пред выбран1 выбран2
20:
21: факт добавить s;вершина;обозначение_вершины s;ребро;обозначение_вершины_1;обозначение_вершины_2
22:
23: присвоить ширина_пред '' список_высота_выбраны_пред {}
24: для ширина (список сгенерить $результат 1 [ШИРИНА_МАКС] )
25: список сгенерить список_высота 1 [ВЫСОТА_МАКС]
26: присвоить список_высота_выбраны {}
27:
28:
29: для (список сгенерить $результат 1 (список выбратьСлучайный $результат [список_высота] ) )
30: список выбратьСлучайный выбран [список_высота]
31: список сцепить список_высота_выбраны $ [выбран]
32: множество разность список_высота $ [выбран]
33: следующий
34:
35:
36: список упорядочитьЧисла список_высота_выбраны $
37: присвоить предыдущая_вершина ''
38: для [список_высота_выбраны]
39: факт добавить "r;вершина;{[ширина];[$ОбъектЦикла]}"
40: если [предыдущая_вершина] != ''
41: факт добавить "r;ребро;[предыдущая_вершина];{[ширина];[$ОбъектЦикла]}"
42: конец
43: присвоить предыдущая_вершина "{[ширина];[$ОбъектЦикла]}"
44: следующий
45:
46:
47: если [список_высота_выбраны_пред]
48: список выбратьСлучайный выбран1 [список_высота_выбраны_пред]
49: список выбратьСлучайный выбран2 [список_высота_выбраны]
50: факт добавить "r;ребро;{[ширина_пред];[выбран1]};{[ширина];[выбран2]}"
51: конец
52:
53: присвоить ширина_пред [ширина] список_высота_выбраны_пред [список_высота_выбраны]
54: если [ширина] == 1
55: список выбратьСлучайный выбран [список_высота_выбраны]
56: присвоить НАЧАЛЬНАЯ_ВЕРШИНА "[ширина];[выбран]"
57: конец
58: если [ширина] == [ШИРИНА_МАКС]
59: список выбратьСлучайный выбран [список_высота_выбраны]
60: присвоить КОНЕЧНАЯ_ВЕРШИНА "[ширина];[выбран]"
61: конец
62: следующий
63:
64:
65: возврат
66:
67: функция Найти_путь
68: память локальный ПРОСМОТРЕТЬ ПРОСМОТРЕНЫ ТЕКУЩАЯ_ВЕРШИНА СМЕЖНЫЕ_ВЕРШИНЫ \
69: родители_ПРОСМОТРЕТЬ родители_ПРОСМОТРЕНЫ родитель_ТЕКУЩАЯ_ВЕРШИНА \
70: позиция вершина
71:
72: >Демонстрация алгоритма поиска пути на графе.
73: >Задача: Найти путь от вершины {[НАЧАЛЬНАЯ_ВЕРШИНА]} до {[КОНЕЧНАЯ_ВЕРШИНА]}.
74:
75: присвоить НАЙДЕН_ПУТЬ {}
76: присвоить ПРОСМОТРЕТЬ "{[НАЧАЛЬНАЯ_ВЕРШИНА]}" ПРОСМОТРЕНЫ {}
77: присвоить родитель_ТЕКУЩАЯ_ВЕРШИНА {} родители_ПРОСМОТРЕТЬ "{[родитель_ТЕКУЩАЯ_ВЕРШИНА]}" родители_ПРОСМОТРЕНЫ {}
78: пока [ПРОСМОТРЕТЬ] != {}
79: список голова ТЕКУЩАЯ_ВЕРШИНА [ПРОСМОТРЕТЬ]
80: список голова родитель_ТЕКУЩАЯ_ВЕРШИНА [родители_ПРОСМОТРЕТЬ]
81: список удалить ПРОСМОТРЕТЬ $ 1 1
82: список удалить родители_ПРОСМОТРЕТЬ $ 1 1
83: если [ТЕКУЩАЯ_ВЕРШИНА] == [КОНЕЧНАЯ_ВЕРШИНА]
84: присвоить НАЙДЕН_ПУТЬ "{[ТЕКУЩАЯ_ВЕРШИНА]}"
85: пока [родитель_ТЕКУЩАЯ_ВЕРШИНА] != {}
86: список сцепить НАЙДЕН_ПУТЬ $ "{[родитель_ТЕКУЩАЯ_ВЕРШИНА]}"
87: список найти позиция [ПРОСМОТРЕНЫ] [родитель_ТЕКУЩАЯ_ВЕРШИНА]
88: список взять родитель_ТЕКУЩАЯ_ВЕРШИНА [родители_ПРОСМОТРЕНЫ] [позиция]
89: цикл
90: список инвертировать НАЙДЕН_ПУТЬ $
91: присвоить ПРОСМОТРЕТЬ {}
92: >Решение: [НАЙДЕН_ПУТЬ].
93: иначе
94:
95: множество или СМЕЖНЫЕ_ВЕРШИНЫ \
96: (факт сопоставитьМножество $результат "r;ребро;{[ТЕКУЩАЯ_ВЕРШИНА]};[?смежные]" ) \
97: (факт сопоставитьМножество $результат "r;ребро;[?смежные];{[ТЕКУЩАЯ_ВЕРШИНА]}" )
98: список сцепить ПРОСМОТРЕНЫ $ "{[ТЕКУЩАЯ_ВЕРШИНА]}"
99: список сцепить родители_ПРОСМОТРЕНЫ $ "{[родитель_ТЕКУЩАЯ_ВЕРШИНА]}"
100: для [СМЕЖНЫЕ_ВЕРШИНЫ]
101: если (список найти $результат [ПРОСМОТРЕТЬ] [$ОбъектЦикла] )
102: иначе
103: если (список найти $результат [ПРОСМОТРЕНЫ] [$ОбъектЦикла] )
104: иначе
105: список сцепить ПРОСМОТРЕТЬ $ "{[$ОбъектЦикла]}"
106: список сцепить родители_ПРОСМОТРЕТЬ $ "{[ТЕКУЩАЯ_ВЕРШИНА]}"
107: конец
108: конец
109: следующий
110: конец
111: цикл
112: возврат
113:
114: функция Показать_граф
115: память локальный номер_факта Вершина1 Вершина2
116:
117:
118: присвоить $цветЛинии [ЦВЕТ_РЕБРА] $толщинаЛинии 1
119: присвоить номер_факта 1
120: пока [номер_факта] <= [$КоличествоФактов]
121: если (список сопоставить $результат (факт взять $результат [номер_факта] ) "r;ребро;[?Вершина1];[?Вершина2]" )
122: Рисовать_линию [Вершина1] [Вершина2]
123: конец
124: увеличить номер_факта
125: цикл
126:
127:
128: присвоить $цветЛинии [ЦВЕТ_ВЕРШИНЫ_ВЫД] $толщинаЛинии 5
129: для [НАЙДЕН_ПУТЬ]
130: если (список размер $результат [$СписокЦикла] ) > 0
131: Рисовать_линию [$ОбъектЦикла] (список голова $результат [$СписокЦикла] )
132: конец
133: следующий
134:
135:
136: присвоить $цветЛинии [ЦВЕТ_ВЕРШИНЫ] $цветКисти [ЦВЕТ_ВЕРШИНЫ]
137: для (факт домен $результат вершина обозначение_вершины )
138: Рисовать_вершину [$ОбъектЦикла]
139: следующий
140:
141:
142: присвоить $цветЛинии [ЦВЕТ_ВЕРШИНЫ_ВЫД] $цветКисти [ЦВЕТ_ВЕРШИНЫ_ВЫД]
143: Рисовать_вершину [НАЧАЛЬНАЯ_ВЕРШИНА]
144: Рисовать_вершину [КОНЕЧНАЯ_ВЕРШИНА]
145: возврат
146:
147: функция Рисовать_вершину вершина
148: память локальный ширина высота ширина0 высота0 ширина1 высота1 ширина2 высота2
149: список сопоставить _ [вершина] "[?ширина];[?высота]"
150: вычислить * ширина0 [ширина] [ШАГ_РЕШЕТКИ]
151: вычислить * высота0 [высота] [ШАГ_РЕШЕТКИ]
152: вычислить - ширина1 [ширина0] [РАДИУС_ВЕРШИНЫ]
153: вычислить - высота1 [высота0] [РАДИУС_ВЕРШИНЫ]
154: вычислить + ширина2 [ширина0] [РАДИУС_ВЕРШИНЫ]
155: вычислить + высота2 [высота0] [РАДИУС_ВЕРШИНЫ]
156: рисовать круг [ширина1] [высота1] [ширина2] [высота2]
157: рисовать текстВПрямоугольнике [ширина1] [высота1] [ширина2] [высота2] "{[ширина];[высота]}"
158: возврат
159:
160: функция Рисовать_линию вершина1 вершина2
161: память локальный ширина1 высота1 ширина2 высота2
162: список сопоставить _ [вершина1] "[?ширина1];[?высота1]"
163: список сопоставить _ [вершина2] "[?ширина2];[?высота2]"
164: вычислить * ширина1 $ [ШАГ_РЕШЕТКИ]
165: вычислить * высота1 $ [ШАГ_РЕШЕТКИ]
166: вычислить * ширина2 $ [ШАГ_РЕШЕТКИ]
167: вычислить * высота2 $ [ШАГ_РЕШЕТКИ]
168: рисовать линия [ширина1] [высота1] [ширина2] [высота2]
169: возврат